1. Field of the Invention
The present invention relates in general to the field of information processing, and more specifically to a system and method for processing complex configuration problems using configuration sub-models.
2. Description of the Related Art
Computer assisted product configuration continues to offer substantial benefits to a wide range of users and industries. FIG. 1 depicts a conventional product configuration process 100 performed by a configuration engine 101. The configuration process 100 represents one embodiment of an inference procedure. In one embodiment of a conventional inference procedure, configuration query 102 is formulated based on user configuration input, a configuration engine performs the configuration query 102 using a configuration model 104, and the configuration engine provides an answer 106 to the configuration query 102 based on the configuration query 102 and the contents of the configuration model 104. The answer 106 represents a particular response to the configuration query 102.
A configuration model 104 uses, for example, data, rules, and/or constraints (collectively referred to as “data”) to define compatibility relationships between parts (also commonly referred to as “features”) contained in a specific type of product. A part represents a single component or attribute from a larger, more complex system. Parts may be combined in different ways in accordance with rules and/or constraints to define different instances of the more complex system. For example, “V6 engine” or the exterior color “red” can be parts on a vehicle, and a specific hard disk drive can be a part on a computer. A part group, also called a group, represents a collection of related parts. For example, an “Engines” group might contain the parts “V6 engine” and “4 cylinder engine”. A product configuration is a set of parts that define a product. For example, a vehicle configuration containing the parts “V6 engine” and “red” represents a physical vehicle that has a red exterior and a V6 engine. A product can be a physical product such as a vehicle, computer, or any other product that consists of a number of configurable features such as an insurance product. Additionally, a product can also represent a service. A configuration query (also referred to as a “query”) is essentially a question that is asked about the parts and relationships in a configuration model. The answer returned from a configuration query will depend on the data in the configuration model, the approach used for answering the question, and the specifics of the question itself. For example, one possible configuration query, translated to an English sentence, is the following: For the given configuration model, are the parts “red” and “V6 engine” compatible with each other.
The configuration model 104 can be used to determine, for example, which parts are compatible with other parts, and provide additional details around specific relationships. For example, a vehicle configuration model can indicate that “red” (a part) is the standard color feature for a specific vehicle, but that the color red is not compatible with “V6 engine” (a part). Configuration model 104 may also contain additional information needed to support specific product related queries. Configuration models can be developed in any number of ways. U.S. Pat. No. 5,825,651 entitled “Method and Apparatus for Maintaining and Configuring Systems”, inventors Gupta et al., and assigned to Trilogy Development Group, Inc., describes an example configuration engine and rules based configuration model. U.S. Pat. No. 5,825,651 is incorporated herein by reference in its entirety. U.S. Pat. No. 5,515,524 entitled “Method and Apparatus for Configuring Systems”, inventors John Lynch and David Franke, and assigned to Trilogy Development Group, Inc., describes another example configuration engine and constraint based configuration model. U.S. Pat. No. 5,515,524 is also incorporated by reference in it entirety.
FIG. 2 depicts an example configuration model 200 of a product represented in a graphical, tree based form. The product can be configured to include part combinations A1, B1 or B2, C1, X1 or X2, and Y1 or configured to include part combinations A2, B2, C2, X2, and Y1 or Y2. The configuration model 200 includes rules to define these part relationships. Table 1 represents an example rule set, wherein “S” represents “standard” and “O” represents optional. Configuration model 200 represents a relatively non-complex configuration model. Actual configuration models for a single product can include hundreds of thousands or more parts and rules.
TABLE 1Example Configuration Rules for a ProductA1 S ALLA2 O ALLB1 S A1B2 S A2B2 O A1C1 S A1C2 S A2X1 S C1X2 S C2X2 O C1Y1 O C1Y1 S C2Y2 S C1
Solving configuration problems using computer assisted technology often requires a significant amount of data processing capabilities. Consequently, configuration technologies have attempted to exploit increased data processing capabilities, memory capacities, and network data transfer throughput rates by increasing the capabilities of the configuration engines and/or enhancing the complexity of configuration models and configuration queries. The complexity of a configuration model can be defined in any number of ways, such as by the diversity of parts, part groups, rules, and constraints supported by the configuration model, by the number of parts, rules, and constraints, and by the complexity of part and part group relationships defined by configuration rules and constraints. In any event, the practical complexity achievable for configuration models has been limited by the ability of computer systems to process data within a given period of time, T, and/or limited by other processing constraints, such as a lack of memory. The time period, T, represents an amount of time considered reasonable to perform a configuration task. Time T can vary depending upon the application and expectation of configuration system users.
FIG. 3 depicts a graph 300 representing the practical limitations of configuration model and configuration query complexity in terms of data processing capabilities. Graph 300 compares data processing capabilities of a particular computer system being used to configure a product versus configuration model and query complexity. Conventional inference procedures, such as configuration processes, have an exponential complexity associated with them as depicted by exponential performance curve 302. Sufficient data processing capability exists to process a configuration model and configuration query having the complexity represented by point A. The dashed line 304 represents the maximum data processing capability of the particular computer system being used. Thus, the computer system could not reasonably process configuration models and configuration queries having a complexity represented by point B.